package jago02.jago0201.ag01_sort;

/**
 * 选择排序
 * 杂化简：多轮遍历无序数组，每次将最小值放到无序数组的首位
 * 解目录：
 *      0.将数组分为有序数组和无序数组，左边为有序数组，右边为无序数组
 *      1.初始无序数组范围为 i-n(i默认0,i最多为数组倒数第二位，n默认数组长度)
 *      2.无序数组开始位i默认为最小索引位
 *      3.无序数组内依次比较元素和最小索引位元素大小，若小于，则更新最小元素索引为该元素索引，最后将最小索引对应的元素交换到i位置
 *      3.i不再属于无序数组，无序数组长度起始位置限更新为i=i+1，继续下轮比较
 * 复杂度：O(N~2)
 */
public class Sort02_Choice {
    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,7,9};
        sort(arr);
        for (Comparable i : arr) {
            System.out.print(i+" ");
        }
    }

    private static void sort(Comparable[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (bigThan(arr[minIndex],arr[j])){
                    minIndex = j;
                }
            }
            exch(arr,minIndex,i);
        }
    }

    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean bigThan(Comparable m, Comparable n) {
       return m.compareTo(n)>0;
    }
}
